package com.njupt.Sort;

import java.util.Arrays;
import java.util.HashMap;

/**
 * @Author: wujiaming
 * @CreateTime: 2024/11/18 15:52
 * @Description: 堆排序
 * @Version: 1.0
 */


public class HeapSort {

    public void buildHeap(int[] nums,int len){
        for (int i = len/2; i > 0 ; i--) {
            headJust(nums,i,len);
        }
    }

    private void headJust(int[] nums, int k, int len) {
        nums[0] = nums[k];
        for (int i = 2*k; i <=len ; i *= 2) {
            if(i<len && nums[i]<nums[i+1]){
                i++;
            }
            if(nums[0]>=nums[i]){
                break;
            }else {
                nums[k] = nums[i];
                k = i;
            }
        }
        nums[k] = nums[0];
    }

    public void heapSort(int[] nums,int len){
        buildHeap(nums,len);
        for (int i = len; i >=1 ; i--) {
            int temp = nums[1];
            nums[1] = nums[i];
            nums[i] = temp;
            headJust(nums,1,i-1);
        }
    }


    public static void main(String[] args) {
        int[] nums = {-1,1,7,5,2,4,3,10,20,19,18};

        HeapSort test = new HeapSort();
        test.heapSort(nums,10);
        System.out.println(Arrays.toString(nums));
    }
}
